//题目链接：https://leetcode.cn/problems/sort-an-array/

class Solution 
{
public:
    vector<int> sortArray(vector<int>& nums) 
    {
        srand(time(NULL));//种一颗随机数种子
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int begin,int end)
    {
        if(begin>=end) return;
        int key=getRandom(nums,begin,end);
        //[0~left]    [left+1,cur-1]   [cur,right-1]  [right,end]
        //  <key           ==key           待处理         >key             
        int cur=begin,left=begin-1,right=end+1;
        while(cur<right)
        {
            if(nums[cur]<key)
                swap(nums[++left],nums[cur++]);
            else if(nums[cur]==key)
                cur++;
            else
                swap(nums[--right],nums[cur]);
        }
        qsort(nums,begin,left);
        qsort(nums,right,end);
    }
    int getRandom(vector<int>& nums,int begin,int end)
    {
        int n=rand();
        return nums[n%(end-begin+1)+begin];
    }
};